package com.minigame.leetCode;

import java.util.Arrays;

/**
 * 给你两个单词word1 和word2，请你计算出将word1转换成word2 所使用的最少操作。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 删除[1]一个字符
 * 插入[2]一个字符
 * 替换[3]一个字符
 *
 * 示例：
 * 输入：word1 = "intention", word2 = "execution"
 * 输出：[3,3,1,3,2]
 * 解释：
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * intention -> inention (删除 't')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 */
public class LeastOperators {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(dp("intention", "execution")));
    }
    /**
     * 考虑动态规划, 三维数组中,第一维为word1, 第二维为word2, 第三维为其对应操作集合, 如[1-删除, 2-插入, 3-替换]
     * 1.边界条件:
     *   1.1 word1 为空, word2 不为空串 dp[0][i] = {2,2,2,...}
     *   1.2 word1 不为空, word2 为空串 dp[i][0] = {1,1,1,...}
     * 2.状态方程
     *   ? ? -> ?a ? 删除 dp[i][j] 在 dp[i-1][j] 的基础上增加删除操作
     *   ? ? -> ? ?b 插入 dp[i][j] 在 dp[i][j-1] 的基础上增加插入操作
     *   ? ? -> ?a ?a 无操作 dp[i][j] 即为 dp[i-1][j-1]
     *   ? ? -> ?a ?b 替换 dp[i][j] 在 dp[i-1][j-1] 的基础上增加替换操作
     * 3.填表
     * 4.返回 dp[i][j]
     */
    public static int[] dp(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][][] dp = new int[m+1][n+1][];
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = new int[i];
            for (int j = 0; j < i; j++) {
                dp[i][0][j] = 1;
            }
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = new int[i];
            for (int j = 0; j < i; j++) {
                dp[0][i][j] = 2;
            }
        }
        //填表
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                int down = dp[i - 1][j].length + 1;
                int left = dp[i][j - 1].length + 1;
                int leftDown = dp[i - 1][j - 1].length;
                boolean replace = word1.charAt(i - 1) != word2.charAt(j - 1);
                if(replace){
                    leftDown += 1;
                }
                int min = Math.min(left,Math.min(down,leftDown));
                if (min == down) {
                    dp[i][j] = Arrays.copyOf(dp[i - 1][j], down);
                    dp[i][j][down - 1] = 1;
                } else if (min == left) {
                    dp[i][j] = Arrays.copyOf(dp[i][j - 1], left);
                    dp[i][j][left - 1] = 2;
                } else if (replace) {
                    dp[i][j] = Arrays.copyOf(dp[i - 1][j - 1], leftDown);
                    dp[i][j][leftDown - 1] = 3;
                } else {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}
